package l.l.w.CodingInterviews;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by llw on 2018/4/12/0012.
 */
public class 序列化二叉树 {
    String Serialize(TreeNode root) {
        if(root == null)return "";
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        StringBuilder sb = new StringBuilder();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(sb != null){
                sb.append(node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }else{
                sb.append('#');
            }
            sb.append(" ");
        }
        sb.delete(sb.length() - 1, sb.length());
        return sb.toString();
    }
    TreeNode Deserialize(String str) {
        //assert correct
        if(str == null || "".equals(str))return null;
        String[] strs = str.split(" ");
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
        queue.offer(root);
        int i = 1;
        String s = null;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            s = strs[i++];
            if(!"#".equals(s)){
                TreeNode left = new TreeNode(Integer.valueOf(s));
                node.left = left;
                queue.offer(left);
            }
            s = strs[i++];
            if(!"#".equals(s)){
                TreeNode right = new TreeNode(Integer.valueOf(s));
                node.right = right;
                queue.offer(right);
            }
        }
        return root;
    }
    public static void main(String[] args) {
        序列化二叉树 solution = new 序列化二叉树();
        TreeNode root = solution.Deserialize("1 2 3 4 # # 5 6 # 7 # # # # #");
        System.out.println(root);
    }
}
